# -*- coding: utf-8 -*-
"""
Created on Tue Jul  6 19:51:59 2021

@author: 86189
"""

import pandas as pd


class solution:
    def __init__(self, gragh_information, node, OD, OD_reliability, node_reliability, source, target):
        """
        Parameters
        ----------
        gragh_information : 每个节点的邻接点列表集合
            DESCRIPTION.
        node : 节点集合列表
            DESCRIPTION.
        OD : OD对，具体参考表格
            DESCRIPTION.
        OD_reliability : 每条链路的可靠度列表
            DESCRIPTION.
        node_reliability : 节点的可靠度列表
            DESCRIPTION.
        source : 源节点
            DESCRIPTION.
        target : 宿节点
            DESCRIPTION.

        Returns
        -------
        None.

        """
        self.gragh_information = gragh_information
        self.node = node
        self.OD = OD
        self.source = source
        self.target = target
        self.path = [self.source]
        self.select = self.gragh_information[self.node.index(source)]
        self.result = []
        self.result_O = []
        self.convert_result = []
        self.OD_reliability = OD_reliability
        self.node_reliability = node_reliability
        self.realibility = 0
        self.BDD_path = []
        self.new_path = []
        self.common_node = []
        self.pre = []

    def backtrack(self):
        """
        函数说明：回溯算法，返回所有路集

        Returns
        -------
        None.

        """
        if self.path[-1] == self.target:
            self.result = self.result + [self.path]
            self.result_O = self.result_O + [self.path]
            return
        for value in self.select:
            if value in self.path:
                continue
            self.path = self.path + [value]
            self.select = self.gragh_information[self.node.index(value)]
            self.backtrack()
            self.path = self.path[0:-1]
            self.select = self.gragh_information[self.node.index(self.path[-1])]

    def convert(self):
        """
        函数说明：将所有节点列表表示的路集转化为所有链路标号表示的路集合

        Returns
        -------
        None.

        """
        new_result = []
        for i in range(len(self.result)):
            new_result = new_result + [[]]
        for i in range(len(self.result)):
            for j in range(len(self.result[i]) - 1):
                index = self.OD[(self.OD['Source'] == self.result[i][j]) & (
                        self.OD['Target'] == self.result[i][j + 1])].index.tolist()
                if len(index) == 0:
                    index = self.OD[(self.OD['Source'] == self.result[i][j + 1]) & (
                            self.OD['Target'] == self.result[i][j])].index.tolist()
                new_result[i] = new_result[i] + index
        self.convert_result = new_result

    def BDD_findnumber(self):
        """
        函数说明：找路集中出现频率最高的点

        Returns
        -------
        None.

        """
        common_node = []
        for i in self.result:
            common_node = common_node + i
        self.common_node = list(set(common_node))
        max_number = 0
        node_index = ''
        for i in common_node:
            number = 0
            for j in self.result:
                if i in j:
                    number += 1
            if number > max_number:
                max_number = number
                node_index = i
        return node_index

    def BDD_Tree(self, node_select, flag):
        self.pre = self.result_O
        if flag == 1:
            if len(self.result_O) != 0:
                for i in self.result_O:
                    if node_select in i:
                        i.remove(node_select)
                        if len(i) == 0:
                            self.result_O = 1
        else:
            if len(self.result_O) != 0:
                for i in self.result_O:
                    if node_select in i:
                        self.result_O.remove(i)
                        if len(self.result_O) == 0:
                            self.result_O = 0


def process(dataframe1, node):
    """
    函数说明：预处理，目的是得到邻接节点列表

    Parameters
    ----------
    dataframe1 : OD对信息表
        DESCRIPTION.
    node : 节点列表
        DESCRIPTION.

    Returns
    -------
    graph_information : 邻接节点列表
        DESCRIPTION.

    """
    graph_information = [[] for i in node]
    for i in range(len(node)):
        temp = dataframe1['Target'][dataframe1['Source'] == node[i]]
        if len(temp.values.tolist()) != 0:
            graph_information[i] = graph_information[i] + temp.values.tolist()
        temp1 = dataframe1['Source'][dataframe1['Target'] == node[i]]
        if len(temp1.values.tolist()) != 0:
            graph_information[i] = graph_information[i] + temp1.values.tolist()
    return graph_information


class Node:
    def __init__(self, result):
        self.pre = None
        self.left = None
        self.right = None
        self.result = result
        self.pre_node = []


def choose(node1):
    if node1.result != 0 and node1.result != 1:
        common_node = []
        for i in node1.result:
            common_node = common_node + i
        common_node = list(set(common_node))
        max_number = 0
        node_index = ''
        for i in common_node:
            number = 0
            for j in node1.result:
                if i in j:
                    number += 1
                if number > max_number:
                    max_number = number
                    node_index = i
        return node_index
    else:
        return -1


def operator(node1, flag, val):
    if val != -1:
        nos = []
        for i in range(len(node1.result)):
            nos = [node1.result[i].copy()] + nos
        if flag == 1:
            if len(nos) != 0:
                for i in range(len(nos)):
                    if val in nos[i]:
                        nos[i].remove(val)
                for i in nos:
                    if len(i) == 0:
                        nos = 1
                        break
        else:
            if len(nos) != 0:
                flag = 0
                for i in range(len(nos)):
                    if val in nos[i]:
                        nos[i] = []
                for i in nos:
                    if len(i) == 0:
                        flag += 1
                if flag == len(nos):
                    nos = 0
        return nos


def operator_again(node_origin):
    if node_origin.result != 0 and node_origin.result != 1:
        node_index = choose(node_origin)
        val1 = operator(node_origin, 0, node_index)
        node1 = Node(val1)
        node1.pre_node = (node_index, 0)
        node_origin.left = node1
        val2 = operator(node_origin, 1, node_index)
        node2 = Node(val2)
        node2.pre_node = (node_index, 1)
        node_origin.right = node2
        node1.pre = node_origin
        node2.pre = node_origin
        return node1, node2
    else:
        return -1


def reli(node_str, dataframe2):
    temp = list(dataframe2['节点'])
    p = temp.index(node_str)
    val = list(dataframe2['可靠度'])
    return val[p]


if __name__ == '__main__':
    dataframe1 = pd.read_excel('OD对.xlsx')
    dataframe2 = pd.read_excel('节点可靠度.xlsx')
    node = dataframe2['节点'].tolist()
    OD = dataframe1.loc[:, ['Source', 'Target']]
    OD_reliability = dataframe1['可靠度'].tolist()
    node_reliability = dataframe2['可靠度'].tolist()
    graph_information = process(dataframe1, node)
    s = solution(graph_information, node, OD, OD_reliability, node_reliability, 'D1', 'S1')
    s.backtrack()
    result = s.result.copy()
    node_start = Node(result)
    stack = [node_start]
    queue = []
    i = 0
    sum = 1
    while i < sum:
        temp = stack[i]
        if operator_again(temp) != -1:
            temp_list = list(operator_again(temp))
            stack.append(temp_list[1])
            stack.append(temp_list[0])
            sum = sum + 2
        if temp.result == 1:
            queue.append(temp)
        i = i + 1
    path_result = []
    for i in range(len(queue)):
        temp_node = queue[i]
        temp_list = []
        while len(temp_node.pre_node) != 0:
            temp_list = temp_list + [list(temp_node.pre_node)]
            temp_node = temp_node.pre
        path_result = path_result + [temp_list]
    BDD_reliability = 0
    for i in range(len(path_result)):
        temp_reliability = 1
        for j in range(len(path_result[i])):
            if path_result[i][j][1] == 1:
                temp_reliability = temp_reliability * reli(path_result[i][j][0], dataframe2)
            else:
                temp_reliability = temp_reliability * (1 - reli(path_result[i][j][0], dataframe2))
        BDD_reliability = BDD_reliability + temp_reliability
    print(BDD_reliability)
